package cn.com.mdx.collection.queue;

import java.util.Iterator;
import java.util.Random;

/**
 * <p> 双端队列 - 数组实现
 *
 * @author ：huangy
 * @date ：Created in 2020/8/14 5:52 下午
 */
@SuppressWarnings("unchecked")
public class ResizingArrayDeque<Item> implements Iterable<Item> {
    /**
     * 初始化数组默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 队列容量
     */
    private int size;
    /**
     * 队列对象数组
     */
    private Item[] items;
    /**
     * 队列头部指针，用于取队列中的数据
     */
    private int first;

    private int last;

    public ResizingArrayDeque() {
        size = 0;
        first = DEFAULT_CAPACITY / 2 + 1;
        last = first;
        items = (Item[]) new Object[DEFAULT_CAPACITY];
    }

    /**
     * @param item 入队列数据
     * @return void
     * @Author huangy
     * @description //TODO 在队列头部添加数据
     * @date 5:16 下午 2020/8/12
     **/
    public void addFirst(Item item) {
        //数组添加到达队列顶头或者队列容量等于数组容量，将数组容量扩大到原来的2倍
        if (first - 1 < 0 || size == items.length) resize(items.length * 2);
        items[--first] = item;
        size++;
    }

    /**
     * @param item 入队列数据
     * @Author huangy
     * @description //TODO 在队列尾部添加数据
     * @date 5:17 下午 2020/8/12
     **/
    public void addLast(Item item) {
        //数组添加到达队列末尾或者队列容量等于数组容量，将数组容量扩大到原来的2倍
        if (last == items.length || size == items.length) resize(items.length * 2);
        items[last++] = item;
        size++;
    }

    /**
     * @return Item
     * @Author huangy
     * @description //TODO 移除队列头部元素
     * @date 8:46 下午 2020/8/17
     **/
    public Item removeFirst() {
        if (isEmpty()) throw new UnsupportedOperationException("队列为空");
        //移除元素首尾指针重合，或者队列容量为数组容量的1/4，将数组容量缩小为原来的1/2倍
        if (first == last || size == items.length / 4) resize(items.length / 2);
        Item item = items[first];
        items[first++] = null;
        size--;
        return item;
    }

    /**
     * @return Item
     * @Author huangy
     * @description //TODO 移除队列尾部函数
     * @date 8:50 下午 2020/8/17
     **/
    public Item removeLast() {
        if (isEmpty()) throw new UnsupportedOperationException("队列为空");
        //移除元素首尾指针重合，或者队列容量为数组容量的1/4，将数组容量缩小为原来的1/2倍
        if (first == last || size == items.length / 4) resize(items.length / 2);
        Item item = items[--last];
        items[last + 1] = null;
        size--;
        return item;
    }

    /**
     * @return int 队列容量
     * @Author huangy
     * @description //TODO 队列容量
     * @date 5:18 下午 2020/8/12
     **/
    public int size() {
        return size;
    }

    /**
     * @return boolean true 表示空 false 表示不为空
     * @Author huangy
     * @description //TODO 查看队列是否为空
     * @date 5:18 下午 2020/8/12
     **/
    public boolean isEmpty() {
        return size == 0;
    }

    private class ResizingArrayDequeIterator implements Iterator<Item> {
        int index = first;

        @Override
        public boolean hasNext() {
            return index < last;
        }

        @Override
        public Item next() {
            return items[index++];
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new ResizingArrayDequeIterator();
    }

    /**
     * @param arrayLength 要重置的长度
     * @return void
     * @Author huangy
     * @description //TODO 重置数组长度
     * @date 8:55 下午 2020/8/12
     **/
    private void resize(int arrayLength) {
        assert size > items.length;
        Item[] newArray = (Item[]) new Object[arrayLength];
        int j = arrayLength / 4;
        for (int i = first; i < last; i++) {
            newArray[j++] = items[i];
        }
        first = arrayLength / 4;
        last = j - 1;
        items = newArray;
    }

    public static void main(String[] args) {
        ResizingArrayDeque<Integer> resizingArrayDeque = new ResizingArrayDeque<>();
        Random random = new Random();
        int n = 100;
        for (int i = 0; i < 100 ; i++) {
            int j = random.nextInt(n) % 2;
            if(1 == j) resizingArrayDeque.addFirst(i);
            else resizingArrayDeque.addLast(i);
        }
        System.out.println(resizingArrayDeque.removeFirst());
        System.out.println(resizingArrayDeque.removeFirst());
        System.out.println(resizingArrayDeque.removeFirst());
        System.out.println("-------------------------------");
        for (int i = 0; i < 50 ; i++) {
            int j = random.nextInt(n) % 2;
            if(1 == j) System.out.println(resizingArrayDeque.removeFirst());
            else System.out.println(resizingArrayDeque.removeLast());
        }
        System.out.println("-------------------------------");
        System.out.println(resizingArrayDeque.removeLast());
        System.out.println(resizingArrayDeque.removeLast());
        System.out.println(resizingArrayDeque.removeLast());
        System.out.println("-------------------------------");
        for (Integer integer : resizingArrayDeque) {
            System.out.println(integer);
        }
    }
}
